package anbow.math;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 统计指定范围之内的素数的数量 要求输入一个n
 * @author Administrator
 *
 */

public class CountPrime {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(countPrime1(n));
	}
	
	/**
	 * 欧拉算法
	 * @param n
	 * @return
	 */
	public static int countPrimes3(int n) {		
	    //特例处理
		if(n<=1) return 0;
		//max就是n
	    int max = n;
	    
	    int[] prime = new int[max];//存放找到的素数
	    //isPrime 并没有被显示的初始化，默认值是false
	    boolean[] isPrime = new boolean[max+5];//标记下标对应的整数是否是某个素数的倍数，倍数>=2
	    
	    int cnt=0;//素数的个数
	    
	    for(int i=2;i<=max;i++) {
	    	//当前是不是找到了一个素数
	        if(isPrime[i]==false) prime[cnt++]=i;//把当前素数i存放到prime数组地count个位置，然后count+1
	        
	        for(int j=0;j<cnt && i*prime[j]<=max;j++) {
	            isPrime[i*prime[j]] = true;//prime[j]素数的i倍一定是合数
	            if(i%prime[j]==0) break;
	            //i=prime[j]*k,i*prime[j+1] = prime[j]*k*prime[j+1]
	            //i*prime[j+1] 应该被k*prime[j+1]这个数筛掉，因为他有更小的素因子prime[j] 
	        }
	    }
	    return cnt;
	}
	/**
	 * 埃氏筛法Olog(logn)
	 * @param n
	 * @return
	 */
	public static int countPrime2(int n) {
		//特例处理 0 1
		if(n<2) return 0;
		//创建boolean类型的数组，数组元素默认为true，长度是n+1，用于标记每个数字是否为素数
		boolean[] isPrime = new boolean[n+1];
		//数组初始化
		Arrays.fill(isPrime, true);
		//特例处理
		isPrime[0]=false;
		isPrime[1]=false;		
		//埃氏筛法
		for(int i=2;i<=n;i++) {
			if(isPrime[i]==true) {
				//若当前元素为素数，则筛选当前元素的K（k>=2）倍 为 非素数，j是一个倍数
				for(int j=2;i*j<=n;j++) {
					//将i的J倍 置为 false
					isPrime[i*j] = false;
				}
			}
		}
		//统计数量
		int count = 0;
		for(int i=0;i<=n;i++) {
			if(isPrime[i]==true) {
				count++;
			}
		}
		return count;
	}
	
	
	/**
	 * 朴素方式 O(n^2)
	 * @param n  1……n
	 * @return 计数
	 */
	public static int countPrime1(int n) {
		int count = 0;
		for(int i=0;i<=n;i++) {
			if(isPrime(i)) {
				//System.out.println(i);
				count++;
			}
		}
		return count;
	}
	
	public static boolean isPrime(int n) {
		//特例处理 0 1
		if(n<2) return false;
		for(int i=2;i*i<=n;i++) if(n%i==0) return false;
		return true;		
	}

}
